#include <iostream>
#include <queue>

using namespace std;

class MedianFinder
{
private:
    priority_queue<int, vector<int>, less<int>> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    int minToAdd = INT_MAX;
    int size = 0;

public:
    MedianFinder()
    {
    }

    void addNum(int num)
    {
        // 2->2
        // 3->2
        // 4->3
        // size/2+1
        size++;
        if (maxHeap.size() < size / 2 + 1)
        {
            // add element to max heap
            if (minHeap.size() == 0)
            {
                maxHeap.push(num);
            }
            else if (num < minHeap.top())
            {
                maxHeap.push(num);
            }
            else
            {
                maxHeap.push(minHeap.top());
                minHeap.pop();
                minHeap.push(num);
            }
        }
        else
        {
            // hold element in max heap
            // add element to min heap
            if (maxHeap.top() > num)
            {
                minHeap.push(maxHeap.top());
                maxHeap.pop();
                maxHeap.push(num);
            }
            else
            {
                minHeap.push(num);
            }
        }
    }

    double findMedian()
    {
        if (size % 2 == 0)
        {
            int v1 = maxHeap.top();
            maxHeap.pop();
            int v2 = maxHeap.top();
            float v = (v1 + v2) / 2.0;
            maxHeap.push(v1);
            return v;
        }
        else
            return maxHeap.top();
    }
};

int main()
{
    cout << "Code295" << endl;
    MedianFinder medianFinder;
    for (int i = 1; i < 10; i++)
    {
        medianFinder.addNum(i);
        cout << medianFinder.findMedian() << endl;
    }
    return 0;
}